package com.yubest;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * [图片] img/0042.png
 *
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 示例 2：
 *
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/10/18 10:50
 */
public class P0042 {

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(new Solution42().trap(height));

        int[] height2 = {4, 2, 0, 3, 2, 5};
        System.out.println(new Solution42().trap(height2));
    }
}

class Solution42 {

    public int trap(int[] height) {
        return cal(height, 0, height.length - 1);
    }

    private int cal(int[] a, int start, int end) {
        //如果最高的两个为首尾两个元素，则计算结果
        if (end - start <= 1) {
            return 0;
        }
        //获取首尾元素最大值
        int max0 = a[start] > a[end] ? a[start] : a[end];
        //判断是否需要二分
        boolean isCut = false;
        for (int i = start + 1; i < end; i++) {
            //如果存在大于首尾两元素的值，则进行二分
            if (a[i] > max0) {
                isCut = true;
                break;
            }
        }
        if (isCut) {
            //获取从首到尾中，最大的元素及坐标
            int max = a[start + 1];
            int index = start + 1;
            for (int i = start + 2; i < end; i++) {
                if (max < a[i]) {
                    max = a[i];
                    index = i;
                }
            }
            int c1 = cal(a, start, index);
            int c2 = cal(a, index, end);
            return c1 + c2;
        } else {
            int c3 = 0;
            //如果首大于尾，倒序遍历计算
            if (a[start] > a[end]) {
                int t = a[end];
                for (int i = end - 1; i > start; i--) {
                    if (a[i] > t) {
                        t = a[i];
                    } else {
                        c3 += t - a[i];
                    }
                }
            } else {
                int t = a[start];
                for (int i = start + 1; i < end; i++) {
                    if (a[i] > t) {
                        t = a[i];
                    } else {
                        c3 += t - a[i];
                    }
                }
            }
            return c3;
        }
    }
}
